#include <stdio.h>

/* This program finds minimum in a rotated sorted array. The array pivot is the
 * min element.
 *
 * Note: This can't handle duplicates. With duplicates we cannot decide which
 * half to discard, for e.g. if start, mid and end are the same value. This
 * leads to a time of O(n)
 */

void findmin(int start, int end)
{
	int mid = (start + end) / 2;
	printf("check %d - %d\n", start, end);

	if (start == end) {
		printf("Min element %d at %d\n", arr[start], start);
		return;
	} else if (end - start == 1) {
		int min = start;
		if (arr[end] < arr[start])
			min = end;

		printf("Min element %d at %d\n", arr[min], min);
		return;
	}

	/* Determine which half the pivot is in. The pivot is in the left half
	 * if mid element is < start, or right half if mid element is >= start
	 */
	if (arr[mid] < arr[start])
		findmin(start, mid);
	else
		findmin(mid, end);
}

int main(int argc, char **argv)
{
	int end = (sizeof(arr) / sizeof(arr[0])) - 1;

	if (arr[0] < arr[end])
		printf("Array not rotated. Min element %d at 0\n", arr[0]);
	else
		findmin(0, end);

	return 0;
}

